package 简单算法;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-22
 * @Description: 给出一棵二叉树, 返回其中序遍历
 * 样例
 * 样例 1:
 * 输入：{1,2,3}
 * 输出：[2,1,3]
 * 解释：
 * 1
 * / \
 * 2   3
 * 它将被序列化为{1,2,3}
 * 中序遍历
 * 样例 2:
 * 输入：{1,#,2,3}
 * 输出：[1,3,2]
 * 解释：
 * 1
 * \
 * 2
 * /
 * 3
 * 它将被序列化为{1,#,2,3}
 * 中序遍历
 * 挑战
 * 你能使用非递归算法来实现么?
 **/
public class 二叉树的中序遍历 {

    public static void main(String[] args) {
        二叉树的中序遍历 s = new 二叉树的中序遍历();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        System.out.println(s.inorderTraversal(root));
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();

        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            result.add(node.val);

            if (node.right == null) {
                node = stack.pop();
                while (!stack.isEmpty() && stack.peek().right == node) {
                    node = stack.pop();
                }
            } else {
                node = node.right;
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
            }
        }
        return result;
    }
}
